package com.linchong.sort;

/**
 * @BelongsProject:Algorithm
 * @BelongsPackage:com.linchong.sort
 * @Author:linchong
 * @CreateTime:2019-01-05 14:59
 * @Description:计数排序
 * 时间复杂度：O(n+k),k是数据范围
 * 空间复杂度：O(n+k)  辅助数组O(n),辅助计数数组O(k)
 * 稳定算法
 */
public class CountingSort {

    public static void countingSort(int [] a,int n){
        if(n<=1) return;
        //查找数据范围
        int max = a[0];
        for(int i = 1;i<n;i++){
            if(max<a[i]){
                max = a[i];
            }
        }
        //申请计数数组，大小为[0,max]
        int[] c = new int[max+1];
        //初始化计数数组数据
        for(int i = 0; i < n; i++){
            c[i] = 0;
        }
        //计算每个元素，放入计数数组中
        for(int i = 0;i<n;i++){
            c[a[i]]++;
        }
        //统计数据放入到计数数组中
        for(int i = 0;i<n;i++){
            c[i] = c[i]+c[i-1];
        }

        //临时数组，统计排序结果
        int[] r = new int[n];
        //计数排序
        for(int i = n-1;i>=0;i--){
            int index = c[a[i]]-1;  //从后向前，依次获取数据为a[i]的元素在数组中的排序位置
            r[index] = a[i];
            c[a[i]]--;
        }
        //将结果拷贝回a数组
        for(int i = 0;i<n;i++){
            a[i] = r[i];
        }
    }
}
